// bfs 解决最短路问题
// 经典问题 - 边权为 1 的最短路问题，bfs 搜索目标坐标，返回搜索的步数
// 经典问题 - 基因序列变化，字符串每次改变一个字符，变化成最终的基因的最少次数。
// bfs 搜索所有可能变化情况，搜到有效变化，有效次数 + 1

// 例题 2：
// 基因序列可以表示为一条由 8 个字符组成的字符串，其中每个字符都是 'A'、'C'、'G' 和 'T' 之一。
// 假设我们需要调查从基因序列 start 变为 end 所发生的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。
// 如，"AACCGGTT" --> "AACCGGTA" 就是一次基因变化。
// 另有一个基因库 bank 记录了所有有效的基因变化，只有基因库中的基因才是有效的基因序列。（变化后的基因必须位于基因库 bank 中）
// 给你两个基因序列 start 和 end ，以及一个基因库 bank ，请你找出并返回能够使 start 变化为 end 所需的最少变化次数。
// 如果无法完成此基因变化，返回 -1 。
//
//        注意：起始基因序列 start 默认是有效的，但是它并不一定会出现在基因库中。
//
//        示例 1：
//
//        输入：start = "AACCGGTT", end = "AACCGGTA", bank = ["AACCGGTA"]
//        输出：1
//        示例 2：
//
//        输入：start = "AACCGGTT", end = "AAACGGTA", bank = ["AACCGGTA","AACCGCTA","AAACGGTA"]
//        输出：2
//        示例 3：
//
//        输入：start = "AAAAACCC", end = "AACCCCCC", bank = ["AAAACCCC","AAACCCCC","AACCCCCC"]
//        输出：3
//
//
//        提示：
//
//        start.length == 8
//        end.length == 8
//        0 <= bank.length <= 10
//        bank[i].length == 8
//        start、end 和 bank[i] 仅由字符 ['A', 'C', 'G', 'T'] 组成

// 解题思路：
// 使用哈希表搜索基因库中的有效基因以及标记基因
// bfs 搜索有效基因变化，如果是最终基因返回有效变化次数

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

public class MinMutation {
    public int minMutation(String startGene, String endGene, String[] bank) {
        Map<String, Integer> hash = new HashMap<>();
        for(String s : bank) hash.put(s, 1);
        char[] gen = new char[] {'A', 'C', 'G', 'T'};
        Queue<String> queue = new LinkedList<>();
        queue.offer(startGene);
        hash.put(startGene, 0);
        int ret = 0;
        while(!queue.isEmpty()){
            int size = queue.size();
            ret++;
            for(int i = 0; i < size; i++){
                String s = queue.poll();
                for(int j = 0; j < 8; j++){
                    char[] sArr = s.toCharArray();
                    for(int k = 0; k < 4; k++){
                        sArr[j] = gen[k];
                        String tmp = new String(sArr);
                        if(hash.containsKey(tmp) && hash.get(tmp) == 1){
                            if(tmp.equals(endGene)) return ret;
                            queue.offer(tmp);
                            hash.put(tmp, hash.get(tmp) - 1);
                        }
                    }
                }
            }
        }
        return -1;
    }
}
